import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-27
 * Time: 11:32
 */
public class Solution {

    public ArrayList<String> Permutation(String str) {
        int len = str.length();
        ArrayList<String> ans = new ArrayList<>();
        StringBuilder stringBuilder = new StringBuilder();
        boolean[] visited = new boolean[len];
        dfs(ans, stringBuilder, visited, 0, str);
        return ans;
    }

    public void dfs(ArrayList<String> ans, StringBuilder stringBuilder,
                    boolean[] visited, int index, String str){
        int len = str.length();
        // 已经遍历过最后了
        if (index == len){
            ans.add(stringBuilder.toString());
            return ;
        }
        // 注意使用 set 去重
        Set<Character> set = new HashSet<>();
        for (int i = 0;i < len;i++) {
            char c = str.charAt(i);
            // 这个字母还没有被用过
            if (!visited[i] && !set.contains(c)){
                stringBuilder.append(c);
                visited[i] = true;
                set.add(c);
                dfs(ans, stringBuilder, visited, index + 1, str);
                visited[i] = false;
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
            }
        }
    }



    public Set<String> set = new HashSet<>();
    public void swap(char[] arr, int index1, int index2){
        char temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public ArrayList<String> Permutation2(String str) {
        int len = str.length();
        char[] arr = str.toCharArray();
        // Arrays.sort(arr);
        ArrayList<String> ans = new ArrayList<>();
        dfs(arr, 0, ans);
        return ans;
    }

    public void dfs(char[] arr, int index, ArrayList<String> ans){
        String s = String.valueOf(arr);
        if (index == arr.length && !set.contains(s)){
            ans.add(s);
            set.add(s);
            return;
        }
        for (int i = index;i < arr.length;i++) {
            if (arr[index] != arr[i]){
                swap (arr, index, i);
            }
            dfs(arr, index + 1, ans);
            if (arr[index] != arr[i]){
                swap (arr, index, i);
            }
        }
    }
}
